package zw_201_300.zw_268_丢失的数字;

import java.util.Arrays;

class Solution {


    /**
     * 排序
     * 时间复杂度：假定 Arrays.sort 使用的是双轴快排实现。复杂度为 O(nlogn)
     * 空间复杂度：O(logn)
     *
     * @param nums
     * @return
     */
//    public int missingNumber(int[] nums) {
//        Arrays.sort(nums);
//        for (int i = 0; i < nums.length; i++) {
//            if (i != nums[i]) return i;
//        }
//        return nums.length;
//    }

    /**
     * 数组哈希
     * 利用 numsnums 的数值范围为 [0,n][0,n]，且只有一个值缺失，
     * 我们可以直接开一个大小为 n + 1n+1 的数组充当哈希表，进行计数，没被统计到的数值即是答案。
     *
     * @param nums
     * @return
     */
//    public int missingNumber(int[] nums) {
//        int n = nums.length;
//        boolean[] hash = new boolean[n + 1];
//        for (int i = 0; i < n; i++) hash[nums[i]] = true;
//        for (int i = 0; i < n; i++) {
//            if (!hash[i]) return i;
//        }
//        return n;
//    }


    /**
     * 原地哈希
     * 事实上，我们可以将 nums 本身作为哈希表进行使用，将 nums[i] 放到其应该出现的位置（下标） nums[i] 上（nums[i]<n），
     * 然后对 nums 进行检查，找到满足nums[i]不等于i 的位置即是答案，如果不存在 nums[i]不等于i的位置，则 n 为答案。
     *
     * @param nums
     * @return
     */
//    public int missingNumber(int[] nums) {
//        int n = nums.length;
//        for (int i = 0; i < n; i++) {
//            if (nums[i] != i && nums[i] < n) swap(nums, nums[i], i--);
//        }
//        for (int i = 0; i < n; i++) {
//            if (nums[i] != i) return i;
//        }
//        return n;
//    }
//
//    void swap(int[] nums, int i, int j) {
//        int c = nums[i];
//        nums[i] = nums[j];
//        nums[j] = c;
//    }


    /**
     * 作差法
     * 利用 nums 的数值范围为[1,n]，我们可以先计算出 [1,n] 的总和 sum（利用等差数列求和公式），
     * 再计算 nums 的总和 cur，两者之间的差值即是 nums 中缺失的数字。
     * 时间复杂度：O(n)
     * 空间复杂度：O(1)
     *
     * @param nums
     * @return
     */
//    public int missingNumber(int[] nums) {
//        int n = nums.length;
//        int cur = 0, sum = n * (n + 1) / 2;
//        for (int i : nums) cur += i;
//        return sum - cur;
//    }


    /**
     * 异或
     * 找缺失数、找出现一次数都是异或的经典应用。
     * 我们可以先求得 [1,n] 的异或和 ans，然后用 ans 对各个 nums[i] 进行异或。
     * 这样最终得到的异或和表达式中，只有缺失元素出现次数为 1 次，其余元素均出现两次（x⊕x=0），即最终答案 ans 为缺失元素。
     *
     * @param nums
     * @return
     */
    public int missingNumber(int[] nums) {
        int n = nums.length;
        int ans = 0;
        for (int i = 0; i <= n; i++) ans ^= i;
        for (int i : nums) ans ^= i;
        return ans;
    }


}
